package com.mdnote.practice.dp;

import jdk.internal.org.objectweb.asm.tree.MultiANewArrayInsnNode;

/**
 * @author Rhythm-2019
 * @date 2020/10/1
 * @description
 */
public class LCP19 {

    public static void main(String[] args) {
        LCP19 lcp19 = new LCP19();
        int count = lcp19.minimumOperationsPlus("yyy");
        System.out.println(count);
    }

    /**
     * 1. 重复子问题，0到睇i片树叶可能处于三种状态：
     *      状态1. 从0到i都是红色的
     *      状态2. 从0到i有红黄
     *      状态3. 从0到i有红黄红
     *  重复的子问题就是当前的状态 = 上一次的状态 + 当前的元素请看
     * 2. DP数组   dp[i][j]  i 从0到第i个树叶，j 状态 dp[i][j] 转换成该状态需要操作的步骤
     * 3. DP方程
     *      dp[i][0] = dp[i - 1][0] + isYellow(i)
     *      dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + isRed(i)
     *      dp[i][2] = Math.min(dp[i - 1][1], dp[i - 1][2])  + isYellow(i)
     *  4. base case: dp[0][0] = isYellow(i)
     *                dp[0][1] = 0
     *                dp[0][2] = 0
     * @param leaves
     * @return
     */
    public int minimumOperations(String leaves) {
        if (leaves.length() < 3) {
            return 0;
        }
        int[][] dp = new int[leaves.length()][3];
        char[] chars = leaves.toCharArray();
        dp[0][0] = isYellow(0, chars);
        dp[0][1] = dp[0][2] = Integer.MAX_VALUE;
        for (int i = 1; i < chars.length; i++) {
            dp[i][0] = dp[i - 1][0] + isYellow(i, chars);
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + isRed(i,chars);
            dp[i][2] = Math.min(dp[i - 1][1], dp[i - 1][2])  + isYellow(i, chars);
        }
        return dp[chars.length - 1][2];
    }

    private int isRed(int index, char[] chars) {
        return chars[index] == 'r'? 1 : 0;
    }

    private int isYellow(int index, char[] chars) {
        return chars[index] == 'y' ? 1 : 0;
    }

    public int minimumOperationsPlus(String leaves) {
        if (leaves.length() < 3) {
            return 0;
        }
        int[] dp = new int[leaves.length()];
        char[] chars = leaves.toCharArray();
        int dp_i_0 = chars[0] == 'y' ? 1 : 0;
        int dp_i_1 = 100000;
        int dp_i_2 = 100000;
        for (int i = 1; i < chars.length; i++) {
            int t_dp_i_0 = dp_i_0, t_dp_i_1 = dp_i_1, t_dp_i_2 = dp_i_2;
            int is_yellow = chars[i] == 'y' ? 1 : 0;
            int is_red = chars[i] == 'r' ? 1 : 0;
            dp_i_0 = t_dp_i_0 + is_yellow;
            dp_i_1 = Math.min(t_dp_i_0, t_dp_i_1) + is_red;
            dp_i_2 = Math.min(t_dp_i_1, t_dp_i_2)  + is_yellow;
        }
        return dp_i_2;
    }
}
